package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 * 回溯/回调
 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

 示例 1：
 输入：digits = "23"
 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

 示例 2：
 输入：digits = ""
 输出：[]

 示例 3：
 输入：digits = "2"
 输出：["a","b","c"]

 提示：
 0 <= digits.length <= 4
 digits[i] 是范围 ['2', '9'] 的一个数字。
 */
public class LetterCombinationsOfAPhoneNumber {
    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
    }

    public static StringBuilder sb = new StringBuilder();

    public static List list = new ArrayList();

    //回溯算法，回调代替多重for循环，并且去掉末尾字符，100/44
    public static List<String> letterCombinations(String digits) {
        if (digits.length()==0) return list;
        String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backTracking(digits,map,0);
        return list;
    }

    private static void backTracking(String digits,String[] map,int index) {
        //遍历所有数字后记录一次，注意这里要toString，不然会记录sb的地址导致list内的元素都相同，指向同一个sb地址
        if (index == digits.length()) {
            list.add(sb.toString());
            return;
        }
        //每个数字内的字母
        String s = map[digits.charAt(index) - '0'];
        for (int i=0;i<s.length();i++) {
            sb.append(s.charAt(i));
            backTracking(digits,map,index+1);
            //回调结束后删除内层for循环刚加上的字符，继续加下一个
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
